Because the base bones of business works in enterprises are being computerized, most of the enterprises come to have large-scaled databases that hold a great amount of data used in those business works. Those data are important data in terms of the business works, so that it is absolutely essential to prevent those data from being leaked to outside also in terms of protecting personal information. Therefore, it is common to encrypt the data to be held in such large-scaled databases.
A database can be considered as an aggregate of a large number of tables. “Natural joining” herein means to join two tables into one by integrating columns when there are the columns showing same data in the two tables. Hereinafter, a typical method depicted in Non-Patent Document 1 and the like executed for naturally joining two tables in a database in which the held data is encrypted (referred to as an encrypted database hereinafter) will be described. FIG. 11 is an explanatory chart showing the structure of an encrypted database system 901 according to a typical technique regarding the encrypted database. The encrypted database system 901 is constituted with a client terminal 910 and an encrypted database server 950 mutually connected via a LAN (Local Area Network) and the like.
The client terminal 910 has the structure as a typical computer device. That is, the client terminal 910 includes a main computation control module (CPU: Central Processing unit) 911, a recording module 912 for recording data, an input module 913 for accepting operations done by the user, and an output module 914 for presenting processing results to the user, and a communication module 915 for performing data communications with other computers.
In the main computation control module 911, a column encryption unit 921 and an encrypted table natural joining request unit 922 are structured to execute respective functions to be described later as each computer program. Further, in the recording module 912, each of individual private key 931a and private key′931b used in processing to be described later is stored. Furthermore, a table A932 and a table B933 to be the targets of encryption and natural joining are inputted to the input module 913.
The encrypted database server 950 also has the structure as a typical computer device. That is, the encrypted database server 950 includes a main computation control module 951 as the main unit for executing computer programs, a recording module 952 for recording data, and a communication module 953 for performing data communications with other computers.
In the main computation control module 951, an encrypted table natural joining unit 963 and a data reception unit 964 are structured to execute respective functions to be described later as computer programs according to an operation command from the client terminal 910.
Further, an encrypted table A941 and an encrypted table 942 which are encryptions of each of the tables A933 and B934, as well as a public key pkey972a and a public key pkey′972b corresponding, respectively, to the private key key931a and the private key key′931b of the client terminal 910 received by the data reception unit 964 from the client terminal 910 are stored in the recording module 952.
FIG. 12 is an explanatory chart for describing the functions of the column encryption unit 921 shown in FIG. 11 in more details. The column encryption unit 921 includes an encrypting function 921a and a table update function 921b. The encrypting function 921a encrypts a specific column (referred to as column a) of the table A932 by using the private key key931a and outputs a ciphertext 934. The table update function 921b outputs the table in which each data of the column a is replaced with the ciphertext 943 as an encrypted table A941, and transmits it to the encrypted database server 950. In the encrypted database server 950, the data reception unit 964 records those to the recording module 952.
The column encryption unit 921 also outputs an encrypted table B942 in which a specific column (referred to as column b) of the table B933 is replaced with a ciphertext by using a private key key′931b, and records it to the recording module 912. Note that a table identifier 932a=“A” of the encrypted table A941, a column identifier 932c=“a” of the column a, a table identifier 933a=“B” of the encrypted table B942, and a column identifier 933c=“b” of the column b are not the targets of encryption, respectively, so that those are stored to the recording module 952 along with the encrypted table A941 and the encrypted table B942 and also stored to the recording module 912 of the client terminal 910 at the same time.
FIG. 13 is an explanatory chart for describing functions of the encrypted table natural joining request unit 922 shown in FIG. 11 in more details. The encrypted table natural joining request unit 922 issues a natural joining request text 971 for giving a command to naturally join the encrypted table A941 and the encrypted table B942 regarding the column a and the column b based on the table identifier 932a=“A” of the encrypted table A941, the column identifier 932c=“a” of the column a, the table identifier 933a=“B” of the encrypted table B942, and the column identifier 933c=“b” of the column b, and transmits it to the encrypted database server 950. In the encrypted database server 950, the data reception unit 964 upon receiving it operates the encrypted table natural joining unit 963 according to the natural joining request text 971.
FIG. 14 is an explanatory chart for describing functions of the encrypted table natural joining unit 963 shown in FIG. 11 in more details. The encrypted table natural joining unit 963 includes a decoding function 963a, a natural joining function 963b, and a re-encrypting function 963c. The decoding function 963a decodes the data of the column a and the column b encrypted in the encrypted table A941 and the encrypted table B942 by using the public key pkey972a and the public key pkey′972b corresponding to the private key key931a and the private key key′931b, respectively, to acquire the table A931 and the table B933 which are in the state before being encrypted.
The natural joining function 963b performs natural joining of the table A932 and the table B933 regarding the column a of the table A932 and the column b of the table B933 according to the command given by the natural joining request text 971. The re-encrypting function 963c re-encrypts the column a (column b) as the key of the joined table A932 and the table B933, and returns the acquired encrypted table A×B981 to the client terminal 910. The public key pkey972a is used herein for the re-encryption. However, other encryption keys may also be used naturally.
FIG. 15 is an explanatory chart showing an example of the table A932 before being encrypted in the encrypted database management device 910 shown in FIG. 11. In the example shown in FIG. 15, the corresponding relation between the card numbers corresponding to the respective user names are shown by setting the first column of the table A932 as “user names” and the second column as “credit card numbers”.
Regarding the data to be concealed, the encrypted database management device 910 encrypts the target data with an encryption function enc such as Hash function by using the private key “key” for the data to be concealed. FIG. 16 is an explanatory chart showing the encrypted table A941 that is in a state acquired by encrypting the table A932 shown in FIG. 15 done by the column encrypting unit 921 shown in FIG. 11. Here, the second column “credit card numbers” is taken as the target to be concealed, and the data acquired by encrypting a plain text m with an encryption key is expressed as enc (key, m).
The private key “key” is inherently given to each table. Encryption is definite, so that the value of enc (key, m) is uniquely determined when the plain text m and the private key “key” are settled. Note, however, that the encryption function enc is desirable to be an irreversible function such as a Hash function.
With this, even when the encrypted table A941 shown in FIG. 15 is leaked to the outside, the credit card number is not leaked unless the private key “key” is also leaked. Further, for the proper user having the private key “key”, the table can be searched by using the credit card number. For example, when searching the user having the credit card number “12334”, the search can be done by using enc (key, 12334).
As technical documents related thereto, there are following documents. Depicted in Patent Document 1 is an encryption/decoding device which can transmit/receive encrypted information containing key recovery information which can recover a decoding key even when the user loses the decoding key in transmission/reception of encrypted data. Depicted in Patent Document 2 is a natural joining high-speed calculation method which enables high-speed search of a table that is acquired by joining two tables.
Depicted in Patent Document 3 is a joining size evaluation method which is capable of decreasing the calculation cost required for performing equi-joining. Depicted in Patent Document 4 is a database inquiry system which guides the user so that the user can generate a proper SQL (Structured Query Language) text.
Depicted in Non-Patent Document 1 is an existing technique regarding the encrypted database described above. Depicted in Non-Patent Document 2 is a typical content of a database including natural joining of tables.    Patent Document 1: Japanese Unexamined Patent Document 2000-267565    Patent Document 2: Japanese Unexamined Patent Document Hei 02-132559    Patent Document 3: Japanese Unexamined Patent Document Hei 10-124533    Patent Document 4: Japanese Patent Application Publication Hei 09-510565
Non-Patent Document 1: Paul Needham et al., “Oracle Advanced Security Technical White Paper”, Oracle Japan, June 2007, “Searched Sep. 3, 2010”,
Non-Patent Document 2: Hiroyuki Kitagawa, “Database System”, Shokodo, July 1996
With the database, not only necessary data is extracted from a vast amount of data but also a plurality of tables are joined frequently by SQL commands and the like. Even for the encrypted data, it is naturally desired to be able to do calculations for performing natural joining of the tables easily without threatening the security.
However, the encryption key “key” is given inherently to each table as described above, so that different encryption keys are given to different tables. Thus, the same data on different tables are different data when encrypted with different encryption keys. Therefore, in order to perform a calculation for joining different tables regarding the data encrypted by the column encryption unit 921 by using the encrypted database management device 901 shown in FIG. 11, it is necessary to join the data by decoding it once as described above.
This will be described more specifically. FIG. 17 is an explanatory chart regarding an example of a case where the encrypted database management device 901 shown in FIG. 11 performs a calculation for naturally joining a plurality of encrypted tables A941 and B942. FIG. 17A shows the encrypted table A941, FIG. 17B shows the encrypted table B942, and FIG. 17C shows an encrypted table A×B981 acquired by performing natural joining of those tables. The encrypted table A941 shows the corresponding relation between each user and corresponding card numbers, in which the first column is “user names” and the second column is “credit card numbers”. The “credit card numbers” in the second column are encrypted by using the private key key931a. The encrypted table B942 shows the expiration dates of the cards, in which the first column is “credit card numbers” and the second column is “credit card expiration dates”. Further, the “credit card numbers” in the first column are encrypted by using the private key key′931b. 
When the administrator of the database wishes to know the corresponding relation between the “user names” and the “credit card expiration dates”, the administrator issues a natural joining command text 971 by the encrypted table natural joining request unit 922 to naturally join the encrypted table A941 and the encrypted table B942 regarding the column “credit card numbers”. By this processing, it is expected to acquire an encrypted table A×B981 which contains the “user names” in the first column, the “credit card numbers” in the second column, and the “credit card expiration dates” in the third column.
However, the encrypted table A941 and the encrypted table B942 are encrypted with the different private keys key931a and key′931b, so that the data thereof are different data because of the different encryption keys even the data at the stage of being in plain texts are the same data. Thus, the encrypted table natural joining unit 963 cannot use the encrypted data directly as the key for natural joining. In order to perform this processing, it is necessary to perform processing for decoding the column “credit card numbers” by the decoding function 963a shown in FIG. 14.
For the processing, the public keys pkey972a and pkey′972b corresponding to the respective private keys key931a and key′931b for the encrypted table A941 and the encrypted table B942 are required. By using the public keys, it is possible to decode the column “credit card numbers” for performing the processing. However, during the processing, the decoded plain text data is stored in the device, so that there may be a risk of having leakages of the plain text data during that time.
FIG. 18 is an explanatory chart regarding an example of performing a calculation for naturally joining an encrypted table C1001 and an encrypted table D1002 encrypted by utilizing key=key′, i.e., the same encryption key “key” in order to overcome the foregoing issues. FIG. 18A shows the encrypted table C1001, the FIG. 18B shows the encrypted table D1002, and FIG. 18C shows an encrypted table C×D1003 acquired by performing natural joining of those tables. This encryption key may be of a public key type or of a common key type.
The encrypted table C1001 shows the corresponding relation between each user and corresponding card numbers, in which the first column is “user names” and the second column is “credit card numbers”. The “credit card numbers” in the second column are encrypted by using the encryption key “key”. The encrypted table D1002 shows the expiration date of each card, in which the first column is “credit card numbers” and the second column is “black list registered dates”. Further, the “credit card numbers” in the first column are encrypted by using the same encryption key “key” as that of the table C1001.
When the encryption key “key” is the same, the data after being encrypted are the same provided that the data before being encrypted regarding the “credit card numbers” in the second column of the encrypted table C1001 and the “credit card numbers” in the first column of the encrypted table D1002 are the same. Therefore, it is possible to acquire an encrypted table C×D1003 by naturally joining the encrypted table C1001 and the encrypted table D1002 directly without utilizing the decoding function 963a. However, at the same time, this means that even an improper user who does not have the encryption key “key” can perform the processing for acquiring the encrypted table C×D1003 by naturally joining the encrypted table C1001 and the encrypted table D1002 regarding the encrypted data. This is not desirable for managing the encrypted database.
That is, desired is an encrypted database management device with which a plurality of tables regarding the encrypted data can be naturally joined by the user who has the proper encryption key without performing processing for decoding the encrypted data but with which the encrypted data cannot be naturally joined by illegitimate users who do not have the proper encryption key. In addition, it is also required to suppress a large increase in the calculation amount for performing the processing since the database handles a vast amount of data.
Each of the above-described Patent Documents and Non-Patent Documents are not designed to overcome such issue, so that techniques capable of overcoming such issue are not depicted therein naturally.
An object of the preset invention is to provide an encrypted database system, a client terminal, an encrypted database server, a natural joining method, and a program thereof, which are characterized to be capable of naturally joining a plurality of tables of an encrypted database regarding the encrypted data without performing processing for decoding each element of the data and without largely increasing the calculation amount.